package com.yaoli.ajob;

/**
 * Created by will on 2017/4/26.
 */
public class _074_Searcha2DMatrix {
    public static void main(String[] args) {
        _074_Searcha2DMatrix searcha2DMatrix = new _074_Searcha2DMatrix();

        int matrix [][] ={{1,3,5,7},{10,11,16,20},{23,30,34,50}};

        searcha2DMatrix.searchMatrix(matrix,60);

    }

    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix.length == 0 || matrix[0].length == 0){
            return false;
        }

        boolean flag = false;

        int begin = 0 ;
        int end = matrix.length * matrix[0].length - 1;

        int middle = 0;

        int rowLength = matrix[0].length ;
        while(begin <= end){
            middle = (end + begin) / 2;
            int temp = matrix[middle/rowLength][middle%rowLength];
            if(temp == target){
                return true;
            }else if(target < temp){
                end = middle - 1;
            }else {
                begin = middle + 1;
            }
        }

        return  flag;
    }

    public boolean searchMatrix2(int[][] matrix, int target) {
        int rl = matrix[0].length - 1;

        int begin = 0;

        int end = matrix.length - 1;

        int middle =0;

        while(begin <= end){
            middle = (begin + end) / 2;

            int temp = matrix[middle][rl];
            if(temp == target){
                return true;
            }

            if(target < matrix[middle][rl] && target < matrix[middle][0]){
                end = middle - 1;

            }else if(target < matrix[middle][rl] && target >= matrix[middle][0]){
                break;
            }

            if(temp > matrix[middle][rl]){
                begin = middle + 1;
            }
        }

        int row = middle;

        begin = 0 ;
        end = matrix[begin].length - 1;
        boolean flag = false;

        while(begin < end){
            middle = (begin + end) / 2;

            if(target < matrix[row][middle]){
                end = middle - 1;
            }else if(target > matrix[row][middle]){
                begin = middle + 1;
            }else{
                flag = true;
                break;
            }
        }

        return flag;
    }
}
